package com.sgg.algorithm.search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000,1000,1000, 1234};
        System.out.println(binarySearch(arr, 0, arr.length - 1, 9));
        System.out.println(binarySearchMultipart(arr, 0, arr.length - 1, 1000));
    }

    /**
     * @param arr 有序的
     */
    public static int binarySearch(int[] arr, int left, int right, int value) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (arr[mid] > value) {
            return binarySearch(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            return binarySearch(arr, mid + 1, right, value);
        } else {
            return mid;
        }
    }

    //找多个
    public static List<Integer> binarySearchMultipart(int[] arr, int left, int right, int value) {
        if (left > right) {
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        int mid = (left + right) / 2;
        if (arr[mid] > value) {
            return binarySearchMultipart(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            return binarySearchMultipart(arr, mid + 1, right, value);
        } else {
            list.add(mid);
            int temp = mid-1;
            while (true) {
                if (temp <0 || arr[temp] != value) {
                    break;
                }
                list.add(temp);
                temp--;
            }
            temp = mid+1;
            while (true) {
                if (temp == right || arr[temp] != value) {
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }
    }
}
